<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>semidef</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab Function</center>
    <div align="right">Last update : 20/12/2004</div>
    <p>
      <b>semidef</b> -  semidefinite programming</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)  </tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>x0</b>
        </tt>: m x 1 real column vector (must be strictly primal feasible, see below)</li>
      <li>
        <tt>
          <b>Z0</b>
        </tt>: L x 1 real vector (compressed form of a strictly feasible dual matrix, see below)</li>
      <li>
        <tt>
          <b>F</b>
        </tt>: L x (m+1) real matrix</li>
      <li>
        <tt>
          <b>blck_szs</b>
        </tt>:  p x 2 integer matrix (sizes of the blocks) defining the dimensions  of the (square) diagonal blocks <tt>
          <b>size(Fi(j)=blck_szs(j) j=1,...,m+1</b>
        </tt>.</li>
      <li>
        <tt>
          <b>c</b>
        </tt>: m x 1 real vector</li>
      <li>
        <tt>
          <b>options</b>
        </tt>: row vector with five entries <tt>
          <b>[nu,abstol,reltol,0,maxiters]</b>
        </tt>
      </li>
      <li>
        <tt>
          <b>ul</b>
        </tt>: row vector with two entries</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>
      <tt>
        <b>[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)</b>
      </tt>
    solves semidefinite program:</p>
    <pre>


    minimize    c'*x
    subject to  F_0 + x_1*F_1 + ... + x_m*F_m  &gt;= 0

 and its dual
 
    maximize    -Tr F_0 Z
    subject to  Tr F_i Z = c_i, i=1,...,m
                Z &gt;= 0

   
    </pre>
    <p>
    exploiting block structure in the matrices <tt>
        <b>F_i</b>
      </tt>.</p>
    <p>
    It interfaces L. Vandenberghe and S. Boyd sp.c program.</p>
    <p>
    The <tt>
        <b>Fi's</b>
      </tt> matrices are stored columnwise in <tt>
        <b>F</b>
      </tt> in
    compressed format: if <tt>
        <b>F_i^j</b>
      </tt>, i=0,..,m, j=1,...,L denote the jth 
    (symmetric) diagonal block of <tt>
        <b>F_i</b>
      </tt>, then</p>
    <pre>

    [ pack(F_0^1)  pack(F_1^1) ...  pack(F_m^1) ]
    [ pack(F_0^2)  pack(F_1^2) ...  pack(F_m^2) ]
F=  [   ...       ...          ...              ]
    [ pack(F_0^L)  pack(F_1^L) ...  pack(F_m^L) ]
   
    </pre>
    <p>
    where <tt>
        <b>pack(M)</b>
      </tt>, for symmetric <tt>
        <b>M</b>
      </tt>, is the vector 
    <tt>
        <b>[M(1,1);M(1,2);...;M(1,n);M(2,2);M(2,3);...;M(2,n);...;M(n,n)]</b>
      </tt>
    (obtained by scanning columnwise the lower triangular part of <tt>
        <b>M</b>
      </tt>).</p>
    <p>
      <tt>
        <b>blck_szs</b>
      </tt> gives the size of block <tt>
        <b>j</b>
      </tt>, ie, 
    <tt>
        <b>size(F_i^j)=blck_szs(j)</b>
      </tt>.</p>
    <p>
    Z is a block diagonal matrix with L blocks <tt>
        <b>Z^0, ..., Z^{L-1}</b>
      </tt>.
    <tt>
        <b>Z^j</b>
      </tt> has size <tt>
        <b>blck_szs[j] times blck_szs[j]</b>
      </tt>.
    Every block is stored using packed storage of the lower triangular part.</p>
    <p>
    The 2 vector <tt>
        <b>ul</b>
      </tt> contains the primal objective value <tt>
        <b>c'*x</b>
      </tt>
    and the dual objective value <tt>
        <b>-Tr F_0*Z</b>
      </tt>.</p>
    <p>
    The entries of <tt>
        <b>options</b>
      </tt> are respectively:
    <tt>
        <b>nu</b>
      </tt> = a real parameter which ntrols the rate of convergence.
    <tt>
        <b>abstol</b>
      </tt> =   absolute tolerance.
    <tt>
        <b>reltol</b>
      </tt> =  relative tolerance (has a special meaning when negative).
    <tt>
        <b>tv</b>
      </tt>  target value, only referenced if <tt>
        <b>reltol &lt; 0</b>
      </tt>.
    <tt>
        <b>iters</b>
      </tt> =  on entry: maximum number of iterations &gt;= 0, on exit: 
    the number of iterations taken.</p>
    <p>
      <tt>
        <b>info</b>
      </tt>  returns 1 if maxiters exceeded,  2 if absolute accuracy
    is reached, 3 if relative accuracy is reached, 4 if target value is
    reached, 5 if target value is  not achievable;  negative values 
    indicate errors.</p>
    <p>
    Convergence criterion:</p>
    <pre>

 (1) maxiters is exceeded
 (2) duality gap is less than abstol
 (3) primal and dual objective are both positive and
     duality gap is less than (reltol * dual objective)
     or primal and dual objective are both negative and
     duality gap is less than (reltol * minus the primal objective)
 (4) reltol is negative and
     primal objective is less than tv or dual objective is greater
     than tv
   
    </pre>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

F0=[2,1,0,0;
    1,2,0,0;
    0,0,3,1
    0,0,1,3];
F1=[1,2,0,0;
    2,1,0,0;
    0,0,1,3;
    0,0,3,1]
F2=[2,2,0,0;
    2,2,0,0;
    0,0,3,4;
    0,0,4,4];
blck_szs=[2,2];
F01=F0(1:2,1:2);F02=F0(3:4,3:4);
F11=F1(1:2,1:2);F12=F1(3:4,3:4);
F21=F2(1:2,1:2);F22=F2(3:4,3:4);
x0=[0;0]
Z0=2*F0;
Z01=Z0(1:2,1:2);Z02=Z0(3:4,3:4);
FF=[[F01(:);F02(:)],[F11(:);F12(:)],[F21(:);F22(:)]]
ZZ0=[[Z01(:);Z02(:)]];
c=[trace(F1*Z0);trace(F2*Z0)];
options=[10,1.d-10,1.d-10,0,50];
[x,Z,ul,info]=semidef(x0,pack(ZZ0),pack(FF),blck_szs,c,options)
w=vec2list(unpack(Z,blck_szs),[blck_szs;blck_szs]);Z=sysdiag(w(1),w(2))
c'*x+trace(F0*Z)
spec(F0+F1*x(1)+F2*x(2))
trace(F1*Z)-c(1)
trace(F2*Z)-c(2)
 
  </pre>
  </body>
</html>
